#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

class Solution:
    """
    @param head: ListNode head is the head of the linked list
    @param m: An integer
    @param n: An integer
    @return: The head of the reversed ListNode
    """
    def reverseBetween(self, head, m, n):
        if m == n:
            return head

        new_head = ListNode(None, head)
        self.head = new_head
        mpre, mnode = self.find_kth_ele(m)
        idx = m
        pre, cur = None, mnode
        while cur:
            next = cur.next
            cur.next = pre

            if idx == n or next is None:
                # 找到需要翻转的最后一个元素cur
                print('match')
                mpre.next = cur
                mnode.next = next
                break

            pre, cur = cur, next
            idx += 1

        return new_head.next

    def find_kth_ele(self, k):
        # return k-1 , kth Node(k and pre of k)
        idx = 0
        node = self.head
        while node:
            if idx+1 == k:
                return node, node.next
            idx += 1
            node = node.next

        return None, None


def show(s):
    n = s
    while(n):
        print("%s ------> " % n.val, sep=' ', end=' ')
        n = n.next


def test():
    n4 = ListNode(4, None)
    n3 = ListNode(3, n4)
    n2 = ListNode(2, n3)
    n1 = ListNode(1, n2)
    s = Solution()
    ret = s.reverseBetween(n1, 2, 2)
    show(ret)

def main():
    # print("start main")
    test()

if __name__ == "__main__":
    main()
